﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Digraphs
{
    public class DirectedCycle
    {
        private bool[] marked;
        private int[] edgeTo;
        private Stack<int> cycle;//有向环中的所有顶点（如果存在）
        private bool[] onStack;//递归调用的栈上的所有顶点

        public DirectedCycle(Digraph G)
        {
            onStack = new bool[G.V()];
            edgeTo = new int[G.V()];
            marked = new bool[G.V()];

            for (int v = 0; v < G.V(); v++)
            {
                if (!marked[v])
                    Dfs(G,v);
            }
        }

        private void Dfs(Digraph G, int v)
        {
            onStack[v] = true;
            marked[v] = true;
            foreach (var w in G.Adj(v))
            {
                if (HasCycle())
                    return;
                else if (!marked[w])
                {
                    edgeTo[w] = v;
                    Dfs(G, w);
                }
                else if (onStack[w])
                {
                    cycle = new Stack<int>();
                    for (int x = v; x != w; x = edgeTo[x])
                        cycle.Push(x);
                    cycle.Push(w);
                    cycle.Push(v);
                }
            }
            onStack[v] = false;
        }

        public bool HasCycle()
        {
            return cycle != null;
        }

        public IEnumerable<int> Cycle()
        {
            return cycle;
        }
    }
}
